#include "ThreadsPool.h"

///#include "Merger.h"
#include <algorithm>

#include <string.h>

#define max(i, j) ((i >= j) ? i : j)
#define min(i, j) ((i <= j) ? i : j)

#define MB()  __asm__ __volatile__ ("lock; addl $0,0(%%esp)" : : : "memory")
#define WMB() __asm__ __volatile__ ("" : : : "memory")


ThreadsPool *pool;

ThreadsPool::ThreadsPool() :
	threads(new pthread_t[maxThreads]),
	threadsData(new ThreadData*[maxThreads])
{
	initializeThreads();
}

ThreadsPool::~ThreadsPool()
{
	/* TODO: correct deletes */
	for (int i = 0; i < maxThreads; i++)
		delete threadsData[i];
	delete[] threadsData;
	delete[] threads;
}

#ifdef	DEBUG
#include <iostream>
using namespace std;
#endif	/* DEBUG */


// TODO - remove at the end
///static pthread_mutex_t lock;





static bool pNameLt(const Match *m1, const Match *m2)
{
	return ((m1->refStart + m1->length < m2->refStart + m2->length) ||  
		(((m1->refStart + m1->length) == (m2->refStart + m2->length)) && ((m1->inputStart - m1->badChars + m1->length) < (m2->inputStart - m2->badChars + m2->length))));
}



static int contained(Match *m1, Match *m2)
{
	// Input sequence of m2 is contained in Input sequence of m1
	if (  (((m1->inputStart < m2->inputStart) &&
		   (m1->inputStart + m1->length >= m2->inputStart + m2->length)))
		||
		  (((m1->inputStart <= m2->inputStart) &&
		   (m1->inputStart + m1->length > m2->inputStart + m2->length))))
	{
		if ((m1->refStart >= m2->refStart + m2->length) ||
			(m2->refStart >= m1->refStart + m1->length))
		{
			// The matches do not overlap
			return 0;
		}
		// They are either overlapping or m2 is strongly contained in m1 => m1 wins
		return 1;
	}
	
	// Input sequence of m1 is contained in Input sequence of m2
	if (  (((m2->inputStart < m1->inputStart) &&
		   (m2->inputStart + m2->length >= m1->inputStart + m1->length)))
		||
		  (((m2->inputStart <= m1->inputStart) &&
		   (m2->inputStart + m2->length > m1->inputStart + m1->length))))
	{
		if ((m2->refStart >= m1->refStart + m1->length) ||
			(m1->refStart >= m2->refStart + m2->length))
		{
			// The matches do not overlap
			return 0;
		}
		// They are either overlapping or m1 is strongly contained in m2 => m2 wins
		return -1;
	}


	// If the input strings are equal
	if ((m1->inputStart == m2->inputStart) && (m1->length == m2->length))
	{
		if ((m2->refStart >= m1->refStart + m1->length) ||
			(m1->refStart >= m2->refStart + m2->length))
		{
			// The matches do not overlap
			return 0;
		}
		else
		{
			// Need to take the one that is further in the sequence
			if (m1->refStart + m1->length > m2->refStart + m2->length)
				return 1;
			return -1;
		}
	
	}

	// If there is overlap
	if (  (((m2->inputStart <= m1->inputStart) &&
		   (m2->inputStart + m2->length > m1->inputStart)))
		||
		  (((m2->inputStart >= m1->inputStart) &&
		   (m2->inputStart < m1->inputStart + m1->length))))
	{
		if ((m2->refStart == m1->refStart) &&
			(m2->length == m1->length))
		{
			if (m1->inputStart > m2->inputStart)
				return 1;
			return -1;
		}
	}



	return 0;

	if ((m2->inputStart <= m1->inputStart) ||
		(m1->refStart >= m2->refStart + m2->length))
	{
		// The matches do not overlap
		return 0;
	}



	// If no overlap
	if ((m2->refStart >= m1->refStart + m1->length) ||
		(m1->refStart >= m2->refStart + m2->length))
	{
		// The matches do not overlap
		return 0;
	}


	
	// The refs overlap or contained in one another

	// If m2 ref string is contained in m1
	if (  (((m1->refStart < m2->refStart) &&
		   (m1->refStart + m1->length >= m2->refStart + m2->length)))
		||
		  (((m1->refStart <= m2->refStart) &&
		   (m1->refStart + m1->length > m2->refStart + m2->length))))
	{
		// m1 wins
		return 1;
	}

	// If m1 ref string is contained in m2
	if (  (((m2->refStart < m1->refStart) &&
		   (m2->refStart + m2->length >= m1->refStart + m1->length)))
		||
		  (((m2->refStart <= m1->refStart) &&
		   (m2->refStart + m2->length > m1->refStart + m1->length))))
	{
		// m2 wins
		return -1;
	}


	return 0;


}

static vector<Match *> *filterVector(vector<Match *> *toFilter)
{
	// Go over the results list and filter out the bad ones
///	cout << "A1" << endl;
	vector<Match *> *filteredVec = new vector<Match *>();
	for (vector<Match*>::iterator itFrom = toFilter->begin(); itFrom != toFilter->end(); itFrom++)
	{
///		cout << "A2" << endl;
		Match *candidate = *itFrom;
		// Update candidate inputStart (accroding to badChars)
		candidate->inputStart -= candidate->badChars;
		vector<Match*>::iterator itFilt = filteredVec->begin();
		for (; itFilt != filteredVec->end(); itFilt++)
		{
			// Compare candidate against all from the filtered vector
			Match *filtElement = *itFilt;
///			cout << "\tcomparing:" << endl << "\t";
///			candidate->print();
///			cout << "\t";
///			filtElement->print();
			int val = contained(candidate, filtElement);
///			cout << "Val is " << val << endl;
			if (val > 0)
			{
///				cout << "Filtereing out match: ";
///				filtElement->print();
				// Candidate wins over filter element - remove the filter element
				filteredVec->erase(itFilt--);
			}
			else if (val < 0)
			{
				// Candidate lost, move to the next candidate
				break;
			}
		}
		if (itFilt == filteredVec->end())
		{
///			cout << "Adding candidate: ";
///			candidate->print();
			filteredVec->push_back(candidate);
		}
	}

	return filteredVec;


}

static void sortFileResults(int fInd, int first, ThreadsPool::ThreadData *td)
{

	ThreadsPool::ThreadData **allTData = td->allThreadsData;
	int badCharsSLN = 0; /* bad chars since last name */
///	Printable currPR = new Printable(allTData[first]->names[0]->name);
	Name *prevName = NULL;
	vector<Name *> allNames;
	Match *lastM = NULL;
	int correction = 0;
	int prevChunk = -1;
	size_t noOverlap= allTData[0]->chunkLengths[fInd] - minMatchLength;
	for (int j=first; j < maxThreads; j++)
	{
		//vector<Name*>::iterator currName = allTData[j].names[fInd].begin();
		for (vector<Name*>::iterator currName = allTData[j]->names[fInd].begin(); currName < allTData[j]->names[fInd].end(); currName++)
		{
/*
			if ((*currName)->name != NULL)
				cout << "curname - " << (*currName)->name << endl;
			else
				cout << "curname is NULL" << endl;
*/
			if (prevName != NULL)
			{
				// the previous name wasn't cut
				if ((*currName)->fromPos >= noOverlap)
				{
///					cout << "Got here!" << endl;
					///prevName = *currName;
					continue;
				}
				// this is continueing a sequence from previous chunk
				if (j > 0 && (*currName)->name == NULL)
				{
					// the previous name was cut
					uint nameLen = strlen(prevName->name);
/*					cout << "pevName naem: " << prevName->name << endl;
					cout << "pevName pos: " << prevName->fromPos << endl;
					cout << "noOverlap: " << noOverlap << endl;
*/
					if ((nameLen > minMatchLength) && (prevName->fromPos + nameLen > allTData[j-1]->chunkLengths[fInd]))
					{
	/*
						cout << "HERE4" << endl;
						///cout << "Here3.1.1" << endl;
						cout << "Length prevName: " << strlen(prevName->name) << endl;
						if (allTData[j]->beginStrs[fInd] == NULL)
							cout << "HERE!!!" << endl;
						cout << "beginStrs: " << allTData[j]->beginStrs[fInd] << endl;
						cout << "Length beginStrs: " << strlen(allTData[j]->beginStrs[fInd]) << endl;
	*/
						char *newNameC = new char[nameLen + strlen(allTData[j]->beginStrs[fInd]) - minMatchLength];
						memcpy(newNameC, prevName->name, nameLen);
						memcpy(newNameC + strlen(prevName->name), allTData[j]->beginStrs[fInd] + minMatchLength, strlen(allTData[j]->beginStrs[fInd]) - minMatchLength);
						prevName->name = newNameC;

						// find how many good characters in 
						int goodInbeginStrs = 0;
						char *cp = allTData[j]->beginStrs[fInd];
						while(cp != NULL)
						{
							if (*cp == 'A' || *cp == 'C' || *cp == 'G' || *cp == 'T')
								goodInbeginStrs++;
						}
						correction -= goodInbeginStrs;
					}
					if (prevChunk == j - 1)
						correction += (noOverlap - prevName->fromPos) - (badCharsSLN - allTData[j - 1]->badMM[fInd]);
					else
						correction += noOverlap - (badCharsSLN - allTData[j - 1]->badMM[fInd]);
					if ((*currName)->matches->size() > 0 && lastM != NULL)
					{
						if (lastM->inputStart + lastM->length == allTData[j-1]->chunkLengths[fInd] && 
								(*currName)->matches->front()->inputStart == 0)
						{
							lastM->length += (*currName)->matches->front()->length - minMatchLength;
							(*currName)->matches->erase((*currName)->matches->begin());
						}
					}
					for (vector<Match*>::iterator currM = (*currName)->matches->begin(); currM < (*currName)->matches->end(); currM++)
					{
///						cout << "Using the following correction: " << correction << endl;
						(*currM)->badChars -= correction;
						prevName->matches->push_back(*currM);
						lastM = (*currM);
					}
				}
				else
				{
					correction = 0;
					// Sort the matches on each sequence-name
					prevName->matches = filterVector(prevName->matches);
					std::sort(prevName->matches->begin(), prevName->matches->end(), pNameLt);
					allNames.push_back(prevName);
					prevName = *currName;
					prevChunk = j;
				}
			}
			else
			{
				prevName = *currName;
				prevChunk = j;
			}
		}
		badCharsSLN = allTData[j]->badCharsSLN[fInd];
		noOverlap= allTData[j]->chunkLengths[fInd] - minMatchLength;
	}

	if (prevName != NULL)
	{
		prevName->matches = filterVector(prevName->matches);
		std::sort(prevName->matches->begin(), prevName->matches->end(), pNameLt);
		allNames.push_back(prevName);
	}




///#ifdef	DEBUG
///	cout << "Final results should be:" << endl;
	for (vector<Name*>::const_iterator it = allNames.begin(); it != allNames.end(); it++)
	{
		///cout << (*it)->name << " (with " << (*it)->matches->size() << " results)" <<  endl;
		cout << (*it)->name << endl;
		for (vector<Match*>::const_iterator mit = (*it)->matches->begin(); mit != (*it)->matches->end(); mit++)
		{
			(*mit)->print();
		}
	}
///#endif	/* DEBUG */
}






















/* A static function that is activated by the pthread_create function.
   Receives a pointer to ThreadData as its argument */
static void *thread_wrapper(void *args)
{
	ThreadsPool::ThreadData *td = (ThreadsPool::ThreadData *)args;
///	Merger *merger = new Merger();
	// TODO - remove at the end
	///pthread_mutex_lock(&lock);
#ifdef	DEBUG
	cout << "Worker thread " << td->id << " starts execution" << endl;
#endif	/* DEBUG */
	/* Parse chunk per file until the end... */
	for (int i=0; i < numOfFiles; i++)
	{
/*
	 	off_t  chunkSize = files[i]->size / maxThreads;
		off_t  fromPos = (off_t) td->id*chunkSize - windowSize;
		off_t  toPos = (off_t) (td->id+1)*chunkSize + windowSize;
*/
		off_t fromPos;
		off_t toPos;

		// if there isn't enough work for all threads
		if (files[i]->pagesNum < maxThreads)
		{
			// Each of the first threads will get a single page
			if (td->id < files[i]->pagesNum)
			{
				fromPos = td->id * pageSize;
				toPos = (td->id + 1) * pageSize + minMatchLength;
			}
			else
			{
				size_t doneChunks = __sync_add_and_fetch(&files[i]->parsedChunks, 1);
				if (doneChunks == maxThreads)
				{
					sortFileResults(i, 0, td);
				}
				// Continue to the next job
				continue;
			}
		}
		else
		{
			// there is enough work for all threads, divide it between them
			fromPos = (td->id * (files[i]->pagesNum / maxThreads)) * pageSize;
			toPos = ((td->id + 1) * (files[i]->pagesNum / maxThreads)) * pageSize;
			int rem = files[i]->pagesNum % maxThreads;
			if (td->id < rem)
			{
				fromPos += (td->id * pageSize);
				toPos += ((td->id + 1) * pageSize);
			}
			else
			{
				fromPos += (rem * pageSize);
				toPos += (rem * pageSize);
			}
			toPos += minMatchLength;
		}
		fromPos = max(0, fromPos);
		toPos = min(toPos, files[i]->size);
#ifdef	DEBUG
		cout << "Worker thread " << td->id << " will work on chunk of size " << (toPos - fromPos) << " bytes from " << fromPos << " to " << toPos << endl;
#endif	/* DEBUG */
//		Parser *parse = new Parser(files[i].fd, fromPos, toPos, 
//														&results[i][td->id], &names[i][td->id], &beginStrs[i][td->id]);
		td->chunkLengths[i] = toPos - fromPos;
		Parser *parser = new Parser(files[i]->fd, fromPos, files[i]->size);
		td->parsedChunks[i] = parser;
		td->beginStrs[i] = parser->parseChunk((toPos - fromPos), td->names[i], td->badCharsSLN[i], td->badMM[i]);
		
		size_t doneChunks = __sync_add_and_fetch(&files[i]->parsedChunks, 1);
		if (doneChunks == maxThreads)
		{
#ifdef	DEBUG
	cout << "File " << files[i]->fname << " was processed" << endl;

			cout << "Printing results before sort" << endl;
			for (int x = 0; x < maxThreads; x++)
			{
				cout << "Print thread " << x << " data" << endl;
				vector<Name *> &v = *(td->allThreadsData[x]->names);
				for (vector<Name *>::iterator nit = v.begin(); nit != v.end(); nit++)
				{
					cout << "fromPos: " << (*nit)->fromPos << endl;
				}
			}

#endif	/* DEBUG */
			sortFileResults(i, 0, td);
///			merger->mergeResults(i, 0, threadsData);
			/* TODO: sort and print matches */
		}
	}
	// TODO - remove at the end
	///pthread_mutex_unlock(&lock);
	return NULL;
}

void ThreadsPool::initializeThreads()
{
	// TODO - remove at the end
	///pthread_mutex_init(&lock, NULL);
#ifdef	DEBUG
	cout << "Initializing " << (maxThreads - 1) << " threads" << endl;
#endif	/* DEBUG */
	for (size_t i = 0; i < maxThreads; i++)
	{
		ThreadData *td = new ThreadData(i);
		td->allThreadsData = threadsData;
		threadsData[i] = td;
	}
	for (size_t i = 0; i < maxThreads - 1; i++)
		pthread_create(&threads[i], NULL, &thread_wrapper, threadsData[i]);
}


void ThreadsPool::runMainThread()
{
#ifdef	DEBUG
	cout << "Main thread also executes jobs" << endl;
#endif	/* DEBUG */
	thread_wrapper(threadsData[maxThreads - 1]);
}

void ThreadsPool::waitThreads()
{
#ifdef	DEBUG
	cout << "Waiting stopping threads" << endl;
#endif	/* DEBUG */
	/* Wait for the worker threads */
	for (size_t i = 0; i < maxThreads - 1; i++)
		pthread_join(threads[i], NULL);
	// TODO - remove at the end
	///pthread_mutex_destroy(&lock);
}

